from functools import cache
from typing import List


# 记忆化搜索
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        # 定义 neg 为 数组中某些元素前面为负号 的总和 , 负数的总和
        # sum-neg:  数组中 正好 的 总和
        # sum-neg-neg=sum-2*neg 正好-负号 = 目标值
        # 则 sum-2*neg=target ===> neg = (sum-target)/2  若neg为奇数 or sum<target 则没有目标值

        total = sum(nums)
        if total < target or (total - target) % 2 == 1:
            return 0
        # 计算需要减去的和 == 背包容量
        neg = (total - target) // 2
        n = len(nums)

        # 正 负 的组合 已经排列好，下面考虑的事，从中是否选择 当前元素
        @cache
        # cnt为 已经选的 容量
        def dfs(i, cnt):
            # 结束判断条件,i要递归到最后
            if i >= n:
                return 1 if cnt == neg else 0
            # 如果当前背包剩余容量 小于 当前加入背包的值
            if neg - cnt < nums[i]:
                # 不选
                return dfs(i + 1, cnt)
            # 当前元素 选 or 不选
            return dfs(i + 1, cnt + nums[i]) + dfs(i + 1, cnt)

        return dfs(0, 0)

